import sys

class Grammar:
	''' Class for gramathics
	
		Create a new gramathic and validate strings
		
		self.production,  is the production dictionary
		
		self.content_table is the table used for validates the strings
		
	'''

	def __init__(self,string,start_production):
		#Generates the production dictionary

		self.production={} # The productions dictionary
		self.first_follow={} # This dictionary contains the calculate first and follow
		self.content_table=[] # Rules of content table
		self.start_production=start_production # The start production of the grammatic
		
		
		'''
		The next lines introduce the prod
		'''
		
		list=string.split(", ") 
		for i in range (len(list)):
			p=list[i].split(" -> ")
			self.production[str(p[0])]=p[1].split("|")
		self.first_n_follow()


	def first_n_follow(self):
		'''Calculates first and the follow in a production
		
			This cycle is for calculate the first and follow production of each key
		
		'''
	
		for key in self.production.keys():
			pair=[]
			pair.append(self.no_repeat(self.first(key)))
			print "First of %s values %s" % (key,pair[0])
			pair.append(self.follow(key))
			print "Follow of %s values %s" % (key,pair[1])
			self.first_follow[key]=pair
		
		self.first_follow[self.start_production][1].append("$") # The first production has $ in the follow  list	
			

	def first(self,t):
		'''
		Follow recursive algorithm, calculates first symbols
		
		The productions are like this one
		
		A - >  B alpha
		
		Just one simple rule
		
		first(A) = first (B)
		
		If B is terminal, returns it self
		
		else (If B is a production) calculates again first(B)
		
		
		'''
		first_list=[] # First list
		if not self.is_terminal(t):  # If t is not terminal	
			for i in range(len(self.production[t])): # Search where can be applied any rules in the productions
				if self.is_terminal(self.production[t][i][0])==1: # Evaluates if t is a terminal symbol
					if self.production[t][i][0]=="^": # It is an identificator?
						first_list.append("^"+self.production[t][i][1:]) # If is true, then returns the entyre id 
					else:
						first_list.append(self.production[t][i][0]) # If is true, then returns the production the first terminal symbol					
				else:
					first_list.extend(self.first(self.production[t][i][0]))	# Else, please search again in the next production. And when search is complete add to first list
		else:
			first_list.append(t) # If t is a terminal, return it self					
		return first_list

	def follow(self,t):
		'''
		Follow recursive algorithm, calculates follow symbols
		This algorithm applies two rules:
		
		The productions are like this one
		
		A - >  alpha B beta
		
		1st rule: 
		
		If first(beta)  doesn't contains epsilon then:
		
		Follow (B) =  First(beta)
		
		Else if
		
		2nd rule:(first(beta) contains epsilon )
		
		Follow(B) = Follow (A) U ( first(beta) - epsilon )
			
		
		'''

		follow_list=[] # Follo list
		for k in self.production.keys():  # Search where can be applied any rules in the productions
			for i in range(len(self.production[k])): # Evaluates if t is a terminal symbol
				if t in self.production[k][i]: #Found this in a production
					index=self.production[k][i].index(t) +1 # Index of next character
					if self.production[k][i][index:]: # If the value have something
						beta=self.production[k][i][index:] # We assing this to beta
						first_beta=self.no_repeat(self.first(beta[0]))# And calculate first beta
					else:
						
						'''
						In this part, the next symbol is empty so we need asign something to beta
						for apply the second rule. The first symbol has   asigned epsilon 
						'''						
						
						beta=self.production[k][i][index-1]	#The next position is empty so we need assign the actual symbol 
						first_beta=["^e"] # No first (symbols) need to be calculate 						
					if beta != k: # This is important, we don't want deadlocks
						if not ("^e" in first_beta): # Beta doesn't contains epsilon
									
							follow_list.extend(first_beta)								
						else:
							if first_beta !="^e":
								follow_list.extend(first_beta)
								follow_list.remove("^e")
							follow_list.extend(self.follow(k))	
		return follow_list
			
			

	def is_terminal(self,key):
		#If the symbols doen't appear in the production keys, the symbol  terminal 
		return(not self.production.has_key(key))	

	def no_repeat(self,string):
		'''
		
		I call this function for prevent repeat symbols
		
		'''		
		i=0
		while i != (len(string)-1):
			while string[i] in string[i+1:]:
				string.pop(string[i+1:].index(string[i])+1)
			i+=1

		return string

'''		def follow(self,i):
		#Follow recursive algorithm
		


		
	def build_table(self):		
		#Calculates content table
			
	def anlayze_string(self,string):	
		#Check if the string is valid
'''		


		
if __name__=="__main__":
	''' 
		Reserved strings:
		^e Epsilon character
		^id Identificator
		=> Asignament production
		| Or
	'''
	
	# This is an example grammar
	
	grammar1=Grammar("A -> CB, B -> +CB|-CB|^e, C -> ED, D -> *ED|/ED|^e, E -> (A)|^num|^id","A")	
	#grammar2=Grammar("S -> ABC, A -> a|aA|CDE|XY, B -> b|bB|EF, C -> cC|^e, D -> CF, E -> aba, F -> bab|^e, X -> aaa, Y -> bbb")	
	#grammar3=Grammar("E -> T+E|T, T -> F*T|F, F -> a|b|(E)")